package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.junit.Test;

public class Q427 {

	/**
	 * @param n: n pairs
	 * @return: All combinations of well-formed parentheses
	 */
	public List<String> generateParenthesis(int n) {
		// write your code here
		List<String> rs = new ArrayList<>();
		Set<String> set = new HashSet<>();
		String s = "";
		search(0, 0, s, set, n);
		rs.addAll(set);
		return rs;
	}

	private void search(int left, int right, String s, Set<String> set, int n) {
		// TODO Auto-generated method stub
		if (left == n && right == n) {
			set.add(new String(s));
		}
		if (right > left) {
			return;
		}
		if (left < n) {
			s += "(";
			search(left + 1, right, s, set, n);
			s = s.substring(0, s.length() -1);
		}
		if (right < n) {
			s += ")";
			search(left, right + 1, s, set, n);
			s = s.substring(0, s.length() -1);
		}
	}

	@Test
	public void testA() {
		List<String> rs = generateParenthesis(5);
		for (String s : rs) {
			System.out.println(s);
		}
	}

}
